/*-------------------------------------------------------------------------
 *
 * rbtree.h
 *	  PostgreSQL 通用红黑树包的接口
 *
 * Copyright (c) 2009-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *		src/include/lib/rbtree.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef RBTREE_H
#define RBTREE_H

/*
 * RBTNode 旨在用作更大结构的第一个字段，
 * 其附加字段携带调用者所需的树条目的有效载荷数据。
 * （该更大结构的总大小会传递给 rbt_create。）RBTNode 在这里被声明
 * 以支持这种用法，但调用者必须将其视为不透明结构。
 */
typedef struct RBTNode
{
	char color;					/* 节点的当前颜色，红色或黑色 */
	struct RBTNode *left;		/* 左子节点，如果没有则为 RBTNIL */
	struct RBTNode *right;		/* 右子节点，如果没有则为 RBTNIL */
	struct RBTNode *parent;		/* 父节点，如果没有则为 NULL（不是 RBTNIL！） */
} RBTNode;

/* 表示整个树的不透明结构 */
typedef struct RBTree RBTree;

/* 可用的树迭代顺序 */
typedef enum RBTOrderControl
{
	LeftRightWalk,				/* 中序：左子节点，节点，右子节点 */
	RightLeftWalk				/* 反中序：右，节点，左 */
} RBTOrderControl;

/*
 * RBTreeIterator 在遍历树时保持状态。这里声明以便调用者可以进行栈
 * 分配，但必须将其视为不透明结构。
 */
typedef struct RBTreeIterator RBTreeIterator;

struct RBTreeIterator
{
	RBTree	   *rbt;
	RBTNode    *(*iterate) (RBTreeIterator *iter);
	RBTNode    *last_visited;
	bool		is_over;
};

/* 由调用者提供的支持函数 */
typedef int (*rbt_comparator) (const RBTNode *a, const RBTNode *b, void *arg);
typedef void (*rbt_combiner) (RBTNode *existing, const RBTNode *newdata, void *arg);
typedef RBTNode *(*rbt_allocfunc) (void *arg);
typedef void (*rbt_freefunc) (RBTNode *x, void *arg);

extern RBTree *rbt_create(Size node_size,
						  rbt_comparator comparator,
						  rbt_combiner combiner,
						  rbt_allocfunc allocfunc,
						  rbt_freefunc freefunc,
						  void *arg);

extern RBTNode *rbt_find(RBTree *rbt, const RBTNode *data);
extern RBTNode *rbt_leftmost(RBTree *rbt);

extern RBTNode *rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew);
extern void rbt_delete(RBTree *rbt, RBTNode *node);

extern void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl,
							  RBTreeIterator *iter);
extern RBTNode *rbt_iterate(RBTreeIterator *iter);

#endif							/* RBTREE_H */
